package newBee.class1;

/**
 * https://leetcode.cn/problems/0ynMMM/description/
 * 柱状图中最大的矩形
 * arr:[6,7,6,8,6,2]
 * *		  1
 * *	  1   1
 * *	1 1 1 1 1
 * *	1 1 1 1 1
 * *	1 1 1 1 1
 * *	1 1 1 1 1
 * *	1 1 1 1 1 1
 * *	1 1 1 1 1 1
 * *    0 1 2 3 4 5
 */
public class Code05_largestRectangleArea {
    public static void main(String[] args) {
        int[] arr = {6, 7, 6, 8, 6, 2};
        int res = largestRectangleArea(arr);
        System.out.println("res = " + res);
    }

    public static int largestRectangleArea(int[] arr) {
        int[] stack = new int[arr.length];
        int r = 0, ans = 0, left;
        for (int i = 0; i < arr.length; i++) {
            // 栈顶 > 下一个元素，则不符合 大压小
            while (r > 0 && arr[stack[r - 1]] >= arr[i]) {
                int k = stack[--r];
                left = r == 0 ? -1 : stack[r - 1];
                // (i-left -1): 计算边界内面积
                ans = Math.max(ans, (i - left - 1) * arr[k]);
            }
            stack[r++] = i;
        }
        while (r > 0) {
            int k = stack[--r];
            left = r == 0 ? -1 : stack[r - 1];
            // 当出最后元素出栈时，计算最低位置长的面积
            ans = Math.max(ans, (arr.length - left - 1) * arr[k]);
        }
        return ans;
    }
}
